package 算法.NiuKe.JZ;

import java.util.ArrayList;
import java.util.List;

/**
 * @author:谢君臣
 * @Date:2021/3/2410:19
 * @version:1.0
 * @function: 给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
 *      如果K>数组的长度，那么返回一个空的数组
 */
public class JZ29 {
    public static void main(String[] args) {
        ArrayList<Integer> list = GetLeastNumbers_Solution(new int[]{4, 5, 1, 6, 2, 7, 3, 8}, 4);
        System.out.println(list);
    }
    public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if (k>input.length)
            return new ArrayList<>();
        ArrayList<Integer> res = new ArrayList<>();
        for (Integer in : input) {
            int index = find(res,in);
            res.add(index,in);
        }
        return new ArrayList<>(res.subList(0, k));
    }
    public static int find(List<Integer> list,int target){
        int l = 0,r=list.size();
        while (l<r){
            int mid = l + (r-l)/2;
            if (list.get(mid)<=target){
                l = mid+1;
            }else {
                r = mid;
            }
        }
        return l;
    }
}
